package fun.ticsmyc.dataStructure;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Ticsmyc
 * @package fun.ticsmyc.dataStructure
 * @date 2020-07-20 14:26
 */
public class 滑动窗口 {

    //leetcode 76 最小覆盖子串  【窗口大小不固定】
    public String minWindow(String s, String t) {
        Map<Character,Integer> need = new HashMap<>();
        Map<Character,Integer> window = new HashMap<>();

        char[] ss =s.toCharArray();
        char[] tt = t.toCharArray();

        //统计需要的字符数
        for(char temp : tt){
            need.put(temp,need.getOrDefault(temp,0)+1);
        }

        int left =0;
        int right =0;
        int valid =0 ;
        //记录最小覆盖子串的起始位置和长度
        int start=0,len =Integer.MAX_VALUE;
        while(right < ss.length){
            //c进入窗口
            char c =ss[right];
            //窗口右移
            right++;
            //更新数据
            if(need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if(window.get(c) .equals(need.get(c))){
                    //有一个字符已经满足了需求
                    valid++;
                }
            }

//            System.out.println(left+"  "+right);
            //判断窗口是否需要收缩
            while(valid == need.size()){
                //更新最小覆盖子串的长度
                if(right - left <len){
                    start= left;
                    len = right-left;
                }

                //d是将要移出窗口的字符
                char d = ss[left];
                //左移窗口
                left++;
                //窗口内数据变更
                if(need.containsKey(d)){
                    if(window.get(d).equals(need.get(d))){
                        valid--;
                    }
                    if(window.get(d) >1){
                        window.put(d,window.get(d)-1);
                    }else{
                        window.remove(d);
                    }
                }
            }
        }
        return len ==Integer.MAX_VALUE ? "" :s.substring(start,start+len);
    }

    /**
     * 567. 字符串的排列
     * 窗口大小固定。
     * 用数组记录。
     * @param s1
     * @param s2
     * @return
     */
    public boolean checkInclusion(String s1, String s2) {
        int[] need = new int[26];
        int cnt =0;
        for(int i=0;i<s1.length() ;++i){
            need[s1.charAt(i)-'a']++;
            if(need[s1.charAt(i)-'a'] ==1) cnt++;
        }
        int[] cur = new int[26];

        char[] str =s2.toCharArray();
        int left =0;
        int right =0;

        while(right < str.length){
            cur[str[right]-'a']++;
            if(cur[str[right]-'a'] == need[str[right]-'a']) cnt--;
            right++; //每次向右扩1
            if(right-left > s1.length()){ //当窗口大小大于被匹配的字符串长度时，缩小窗口
                if(cur[str[left]-'a'] == need[str[left]-'a']) cnt++;   //如果被删除这个字符刚好达到要求，删除后就不能达标
                cur[str[left]-'a']--;
                left++;
            }
            if(cnt ==0){
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        滑动窗口 t = new 滑动窗口();
        System.out.println(t.minWindow("aa","aa"));
    }
}
